The present invention is directed to coordination of the independent motion paths of robots in a working environment used by these robots. In particular it relates to a method of automatic, decentralized coordination of the independent motion paths which can be broken down into segments of a plurality of mobile robots communicating with each other within a specified geographical area, to avoid collisions and to detect and resolve mutual blocking.
When a number of mobile robots share the same working environment account must be taken of the fact that the robots might collide with each other. The danger of a collision generally increases with the number of robots used. To avoid collisions, the motion paths of the individual robots must be coordinated.
Methods of avoiding collisions between robots, in general, are known.
A method in which it is possible to dispense with a communications network between the robots provides for the introduction of traffic rules for example by which collisions are avoided if the rules are observed by all robots. The disadvantage of this method is however that very specific assumptions must then be made about the working environment. This type of method is described, e.g., in S. Kato, s. Nishiyama and J. Takeno “Coordinating Mobile Robots by Applying Traffic Rules”, International Conference on Intelligent Robots and Systems (IRQS), pp. 1535-1541, 1992.
In another method in which a communications network between the robots can also be dispensed with, the robots are equipped with sensors which can detect other robots within a specific area. Whenever a robot detects another robot the point at which the robots might possibly collide is computed and the motion path is modified accordingly to avoid a collision. Since however the motion paths are replanned on a local basis this can result in mutual blockings of the robots (see below) which will not be detected and resolved. This method is described for example in L. Chun, Z. Zhang and W. Chang, A Decentralized Approach to the Conflict-Free Motion Planning for Multiple Mobile Robots, “Int. Conf. on Robotics and Automation (ICRA), pp. 1544-1549, 1999.
Another approach follows procedures in which the motion paths are coordinated by means of a central component. There are basically two options available here, one of which simultaneously creates the central components for collision-free motion paths for all robots involved; the other makes it possible for independently planned motion paths of the robots only to be coordinated subsequently by using the central components. The first method is described for example in J. Barraquand, B. Langlois and J.-C. Latombe “Numerical Potential Field Techniques for Robot Path Planning, IEEE Trans. On System, Man and Cybernetics, Vol. 22(2), pp. 224-241, 1992. An example of the second method can be found in S. Leroy, J. P. Laumond and T. Simeon “Multiple Path Coordination for Mobile Robots: A Geometric Algorithm”, International Joint Conference on Artificial Intelligence (IJCAI), 1999, and M. Bennewitz and W. Burgard, “Coordinating the Motions of Multiple Mobile Robots Using a Probalistic Model”, 8th International Symposium on Intelligent Robotic Systems (SIRS), 2000.
The disadvantage of all these methods which use a central component for coordinating the motion paths is however that they need a global communications network between the robots. Over and above this these methods are computation-intensive and inflexible.
An easier and more adaptable coordination between the robots with a less expensive communications network could be achieved by decentralized algorithms in which there is communication only between pairs of physically adjacent robots.